package org.example.stack;

import javax.swing.*;
import java.util.*;

/**
 * TODO 力扣刷题
 * @Author chaigq
 */
public class LeetCode {

    /**
     *  买卖股票的最佳时机 II
     *  给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
     *
     * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
     *
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 示例 1:
     * 输入: [7,1,5,3,6,4]
     * 输出: 7
     * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     *      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
     *
     * 示例 2:
     * 输入: [1,2,3,4,5]
     * 输出: 4
     * 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     *      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     *      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
     *
     * 示例 3:
     * 输入: [7,6,4,3,1]
     * 输出: 0
     * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     *
     * TODO 只要后一天比前一天大 就把这两天的差值加一下
     */
    public int maxProfit(int[] prices) {

        int sum = 0;
        for (int i = 1; i < prices.length; i ++){
            if (prices[i] > prices[i - 1]){
                sum += prices[i] - prices[i - 1];
            }
        }
        return sum;
    }

    /**
     * 有效的括号
     *
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 注意空字符串可被认为是有效字符串。
     *
     * 示例 1:
     * 输入: "()"
     * 输出: true
     *
     * 示例 2:
     * 输入: "()[]{}"
     * 输出: true
     *
     * 示例 3:
     * 输入: "(]"
     * 输出: false
     *
     * 示例 4:
     * 输入: "([)]"
     * 输出: false
     *
     * 示例 5:
     * 输入: "{[]}"
     * 输出: true
     *
     */
    public static boolean isValid(String s) {
        if (s == null) return true;
        if (s.length() == 1) return false;
        Stack<Character> stack = new Stack<Character>();
        char[] chars = s.toCharArray();
        for (char c : chars){
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            // || 一边都为true才为true，否则为false
            else if(stack.isEmpty()){
                // 说明此时进来的时括号的另一边
                return false;
            }else {
                if (c != stack.pop()){
                    // 栈不为空
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public boolean isValid2(String s) {
        Stack<Character>stack = new Stack<Character>();
        for(char c: s.toCharArray()){
            if(c=='(')stack.push(')');
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        return stack.isEmpty();
    }

    /**
     * 接雨水
     *
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     *
     * 示例 1：
     * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     *
     * 示例 2：、
     * 输入：height = [4,2,0,3,2,5]
     * 输出：9
     *
     */
    public int trap(int[] height) {
        if (height == null) return 0;
        int sum = 0;
        for (int i = 1; i < height.length - 1; i ++){
            int leftMax = 0;
            int rightMax = 0;
            for (int j = 0; j <= i; j ++){
                // 找到左侧最大高度
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int k = i ; k < height.length; k ++){
                rightMax = Math.max(rightMax, height[k]);
            }
            sum += Math.min(leftMax, rightMax) - height[i];
        }
        return sum;
    }

    /**
     * 接近原点的 K 个点
     * 我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
     *
     * （这里，平面上两点之间的距离是欧几里德距离。）
     *
     * 你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
     *
     * 示例 1：
     * 输入：points = [[1,3],[-2,2]], K = 1
     * 输出：[[-2,2]]
     * 解释：
     * (1, 3) 和原点之间的距离为 sqrt(10)，
     * (-2, 2) 和原点之间的距离为 sqrt(8)，
     * 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
     * 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
     *
     * 示例 2：
     * 输入：points = [[3,3],[5,-1],[-2,4]], K = 2
     * 输出：[[3,3],[-2,4]]
     * （答案 [[-2,4],[3,3]] 也会被接受。）
     *  
     * 提示：
     * 1 <= K <= points.length <= 10000
     * -10000 < points[i][0] < 10000
     * -10000 < points[i][1] < 10000
     *
     */
    public int[][] kClosest(final int[][] points, int K) {

        if (K == 0) return null;
        // 对数组进行排序
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] points1, int[] points2) {
                return (points1[0] * points1[0] + points1[1] * points1[1]) - (points2[1] * points2[1] + points2[0] * points2[0]);
            }
        });

        return Arrays.copyOfRange(points, 0, K);
    }

    /**
     * 简化路径
     *
     * 以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
     * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；
     * 两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
     *
     * 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。
     * 此外，规范路径必须是表示绝对路径的最短字符串。
     *
     * 示例 1：
     * 输入："/home/"
     * 输出："/home"
     * 解释：注意，最后一个目录名后面没有斜杠。
     *
     * 示例 2：
     * 输入："/../"
     * 输出："/"
     * 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
     *
     * 示例 3：
     * 输入："/home//foo/"
     * 输出："/home/foo"
     * 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
     *
     * 示例 4：
     * 输入："/a/./b/../../c/"
     * 输出："/c"
     *
     * 示例 5：
     * 输入："/a/../../b/../c//.//"
     * 输出："/c"
     *
     * 示例 6：
     * 输入："/a//b////c/d//././/.."
     * 输出："/a/b/c"
     *
     *
     */
    public String simplifyPath(String path) {
        // 使用split将字符分开后，要么得到空格，要么得到字符，要么得到..或是.
        // 使用栈模拟，遍历字符数组，如果是正常字符，就栈入，如果是..则弹出，如果是.或是空则continue
        // 最后遍历栈，将字符拼接在一起返回即可
        //
        String[] pathArray = path.split("/");
        //分割后的几种情况 空格说明是多出来的/，.. .与目录
        StringBuilder res =new StringBuilder();
        Deque<String> stack = new ArrayDeque<>();
        for(int i=0;i<pathArray.length;i++){
            //2种情况，栈为空或者栈不为空
            if(pathArray[i].length()==0||pathArray[i].equals("."))    continue;
            if(!stack.isEmpty()){
                if(pathArray[i].equals("..")){
                    stack.pop();
                }else{
                    stack.push(pathArray[i]);
                }
            }else{
                if(!pathArray[i].equals(".."))  stack.push(pathArray[i]);
            }
        }
        if(stack.isEmpty())    return res.append('/').toString();
        while(!stack.isEmpty()){
            res.insert(0,stack.pop());
            res.insert(0,'/');
        }
        return res.toString();
    }

    /**
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     *
     *  求在该柱状图中，能够勾勒出来的矩形的最大面积。
     *  以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
     *  图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
     *
     *  示例:
     *  输入: [2,1,5,6,2,3]
     * 输出: 10
     *
     * TODO 思路：
     * 重循环枚举某一根柱子，将其固定为矩形的高度 h。随后我们从这跟柱子开始向两侧延伸，直到遇到高度小于 h 的柱子，
     * 就确定了矩形的左右边界。如果左右边界之间的宽度为 w，那么对应的面积为 w * h。
     *
     */
    public int largestRectangleArea(int[] heights) {
        if (heights == null) return 0;
        int sum = 0;
        for (int i = 0; i < heights.length; i ++){
            // 设置做边界
            int left = i;
            // 设置右边界
            int right = i;
            // 固定矩形高度
            int height = heights[i];
            while (left - 1 >= 0 && heights[left - 1] >= height){
                left --;
            }
            while (right + 1 < heights.length && heights[right + 1] >= height){
                right ++;
            }
            sum = Math.max(sum, (right - left + 1) * heights[i]);
        }
        return sum;
    }

    public static int largestRectangleArea2(int[] heights) {
        // 这里为了代码简便，在柱体数组的头和尾加了两个高度为 0 的柱体。
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length);

        Deque<Integer> stack = new ArrayDeque<>();
        int area = 0;
        for (int i = 0; i < tmp.length; i++) {
            // 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」；
            // 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
            // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积🌶️ ～
            while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
                // pop 出栈，peek返回栈顶元素
                int h = tmp[stack.pop()];
                int peek = stack.peek();
                area = Math.max(area, (i - peek - 1) * h);
            }
            stack.push(i);
        }

        return area;
    }

    /**
     * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     *
     *  示例 1：
     * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"]
     * ,["1","0","0","1","0"]]
     * 输出：6
     * 解释：最大矩形如上图所示。
     *
     *  示例 2：
     * 输入：matrix = []
     * 输出：0
     *
     *  示例 3：
     * 输入：matrix = [["0"]]
     * 输出：0
     *
     *  示例 4：
     * 输入：matrix = [["1"]]
     * 输出：1
     *
     *  示例 5：
     * 输入：matrix = [["0","0"]]
     * 输出：0
     *
     * 提示：
     * rows == matrix.length
     * cols == matrix.length
     * 0 <= row, cols <= 200
     * matrix[i][j] 为 '0' 或 '1'
     *
     * Related Topics 栈 数组 哈希表 动态规划
     * TODO 思路：
     * 这一题的算法本质上和84题Largest Rectangle in Histogram一样，对每一行都求出每个元素对应的高度，
     * 这个高度就是对应的连续1的长度，然后对每一行都更新一次最大矩形面积。那么这个问题就变成了Largest Rectangle in Histogram。
     * 本质上是对矩阵中的每行，均依次执行84题算法。
     *
     */
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        if (matrix[0].length == 0) return 0;
        return 0;
    }

    /**
     * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
     *
     *  示例 1：
     * 输入：root = [1,null,2,3]
     * 输出：[1,3,2]
     *
     *  示例 2：
     * 输入：root = []
     * 输出：[]
     *
     *  示例 3：
     * 输入：root = [1]
     * 输出：[1]
     *
     *  示例 4：
     * 输入：root = [1,2]
     * 输出：[2,1]
     *
     *  示例 5：
     * 输入：root = [1,null,2]
     * 输出：[1,2]
     *
     *  提示：
     *  树中节点数目在范围 [0, 100] 内
     *  -100 <= Node.val <= 100
     *  进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     *  Related Topics 栈 树 哈希表
     *
     * TODO 迭代：就是每一次对过程的重复，而每一次迭代得到的结果会作为下一次迭代的初始值
     * TODO 递归：程序调用自身的方法
     */

     public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
     }
    // 迭代
    public List<Integer> inorderTraversal(TreeNode root) {

         List<Integer> list = new ArrayList<>();
         Deque<TreeNode> stack = new ArrayDeque<>();
         TreeNode cur = root;
         while (cur != null || ! stack.isEmpty()){
             if (cur != null){
                 // 节点不为空
                 stack.push(cur);
                 cur = cur.left;
             }else {
                 // 节点为空
                 cur = stack.pop();
                 list.add(cur.val);
                 cur = cur.right;
             }
         }
         return list;
    }
    List<Integer> inorderTraversalList = new ArrayList<>();
    public List<Integer> inorderTraversal2(TreeNode root) {

        TreeNode cur = root;
        if (cur == null) return inorderTraversalList;
        while (cur != null){
            if (root.left != null) inorderTraversal(root.left);
            inorderTraversalList.add(root.val);
            if (root.right != null) inorderTraversal(root.right);
        }
        return inorderTraversalList;
    }

    /**
     * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     *
     *  例如：
     * 给定二叉树 [3,9,20,null,null,15,7],
     *
     *      3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *
     *
     *  返回锯齿形层次遍历如下：
     *
     *  [
     *   [3],
     *   [20,9],
     *   [15,7]
     * ]
     *
     *  Related Topics 栈 树 广度优先搜索
     */
    // BFS（广度优先遍历）
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // BFS（广度优先遍历）
        // 最直观的方法是 BFS，逐层遍历树。
        // BFS 在每层的默认顺序是从左到右，因此需要调整 BFS 算法以生成锯齿序列。
        // 最关键的是使用双端队列遍历，可以在队列的任一端插入元素。
        // 如果需要 FIFO （先进先出）的顺序，则将新元素添加到队列尾部，后插入的元素就可以排在后面。
        // 如果需要 FILO （先进后出）的顺序，则将新元素添加到队列首部，后插入的元素就可以排在前面。
        // 算法：实现 BFS 的几种算法。
        // TODO 使用两层嵌套循环。外层循环迭代树的层级，内层循环迭代每层上的节点。
        // TODO 也可以使用一层循环实现 BFS。将要访问的节点添加到队列中，使用 分隔符（例如：空节点）把不同层的节点分隔开。分隔符表示一层结束和新一层开始。
        //
        // 在每一层，使用一个空的双端队列保存该层所有的节点。根据每一层的访问顺序，即从左到右或从右到左，决定从双端队列的哪一端插入节点
        //
        if (root == null) return new ArrayList<List<Integer>>();
        // 结果集合
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        // 队列
        // Deque<TreeNode> deque = new ArrayDeque<>();
        LinkedList<TreeNode> deque = new LinkedList<>();
        // 每层集合
        LinkedList<Integer> linkedList = new LinkedList<>();
        // 根据层级判断读取顺序
        boolean bool = true;
        // 将根节点加入集合中
        deque.addLast(root);
        deque.addLast(null);
        // 遍历二叉树
        while (deque.size() > 0) {
            // 弹出队列中第一个节点
            TreeNode treeNode = deque.pollFirst();
            // 判断节点是否为空
            if (treeNode != null) {
                // 将节点值加入list中
                if (bool) {
                    // 从左到右读,将节点放到队列末尾
                    linkedList.addLast(treeNode.val);
                }else {
                    // 从右往左读，将节点放到队列最前边
                    linkedList.addFirst(treeNode.val);
                }
                // 将节点加入对列中
                if (treeNode.left != null) deque.addLast(treeNode.left);
                if (treeNode.right != null) deque.addLast(treeNode.right);
            }else {
                results.add(linkedList);
                // 遍历一层结束，将list集合清空
                linkedList = new LinkedList<Integer>();
                if (deque.size() > 0) deque.addLast(null);
                bool = !bool;
            }
        }
        return results;
    }

    // DFS （深度优先遍历）
    // 在 DFS 遍历期间，将结果保存在按层数索引的全局数组中。即元素 array[level] 存储同一层的所有节点。然后在 DFS 的每一步更新全局数组
    protected void DFS(TreeNode node, int level, List<List<Integer>> results) {

    }
    public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
        // 使用递归实现 DFS 算法。定义一个递归方法 DFS(node, level)，方法参数为当前节点 node 和指定层数 level。该方法共执行三个步骤：
        // 如果是第一次访问该层的节点，即该层的双端队列不存在。那么创建一个双端队列，并添加该节点到队列中。
        // 如果当前层的双端队列已存在，根据顺序，将当前节点插入队列头部或尾部。
        // 最后，为每个节点调用该递归方法。
        return null;
    }

    /**
     * //根据 逆波兰表示法，求表达式的值。
     * //
     * // 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
     * //
     * // 说明：
     * // 整数除法只保留整数部分。
     * // 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
     * //
     * // 示例 1：
     * //
     * // 输入: ["2", "1", "+", "3", "*"]
     * //输出: 9
     * //解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
     * //
     * //
     * // 示例 2：
     * //
     * // 输入: ["4", "13", "5", "/", "+"]
     * //输出: 6
     * //解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
     * //
     * //
     * // 示例 3：
     * //
     * // 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
     * //输出: 22
     * //解释:
     * //该算式转化为常见的中缀算术表达式为：
     * //  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
     * //= ((10 * (6 / (12 * -11))) + 17) + 5
     * //= ((10 * (6 / -132)) + 17) + 5
     * //= ((10 * 0) + 17) + 5
     * //= (0 + 17) + 5
     * //= 17 + 5
     * //= 22
     * //
     * //
     * //
     * // 逆波兰表达式：
     * // 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
     * // 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
     * // 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
     * //
     * // 逆波兰表达式主要有以下两个优点：
     * // 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
     * // TODO 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
     * //
     */
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (String s : tokens){
            switch (s){
                case "+":
                    deque.push(deque.pop() + deque.pop());
                    break;
                case "-":
                    int num = deque.pop();
                    deque.push(deque.pop() - num);
                    break;
                case "*":
                    deque.push(deque.pop() * deque.pop());
                    break;
                case "/":
                    int num2 = deque.pop();
                    deque.push(deque.pop() / num2);
                    break;
                default:
                    deque.push(Integer.valueOf(s));
            }

//            if("+".equals(s)){
//                int a=deque.pop();
//                int b=deque.pop();
//                deque.push(a+b);
//            }
//            else if("-".equals(s)){
//                int a=deque.pop();
//                int b=deque.pop();
//                deque.push(a-b);
//            }else if("*".equals(s)){
//                int a=deque.pop();
//                int b=deque.pop();
//                deque.push(a*b);
//            }else if("/".equals(s)){
//                int a=deque.pop();
//                int b=deque.pop();
//                deque.push(a/b);
//            }else
//                deque.push(Integer.valueOf(s));
        }
        return deque.pop();
    }

    /**
     * //实现一个基本的计算器来计算一个简单的字符串表达式的值。
     * //
     * // 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
     * //
     * // 示例 1:
     * // 输入: "1 + 1"
     * //输出: 2
     * //
     * // 示例 2:
     * // 输入: " 2-1 + 2 "
     * //输出: 3
     * //
     * // 示例 3:
     * // 输入: "(1+(4+5+2)-3)+(6+8)"
     * //输出: 23
     * //
     * // 说明：
     * // 你可以假设所给定的表达式都是有效的。
     * // 请不要使用内置的库函数 eval。
     * //
     */
    // 其实这类表达式求值问题都基本上可以认为有一个通用解:逆波兰式(后缀表达式)
    //后缀表达式也就是操作符放在操作数之后的一种表达方式，其对于计算机来说是最容易理解、计算的。
    //与逆波兰式有关的可以参考 150. 逆波兰表达式求值
    //因为题目给出的是中缀表达式(即我们最常见的表达式),我们只需要将其转换为后缀表达式即可。
    public int calculate(String s) {
        //这个问题适合用栈来解决，因为表达式中包含括号，我们可以使用栈来查找每个子表达式的值。本质上，我们需要延迟处理主表达式，
        // 直到完成对括号种的中间子表达式的求值，我们使用栈来解决它。
        //我们将表达式的元素一个接一个的添加到栈上，直到我们遇到一个右括号 )。然后逐个弹出栈中的元素，在运行时对子表达式进行求值，
        // 直到遇到左括号 ( 为止。
        //我们需要理解 + 和 - 的区别。+ 遵循结合律。例如 A+B+CA+B+C，等价为 (A+B)+C = A+(B+C)(A+B)+C=A+(B+C)。
        // 然后 - 不遵循这个一规则，这是该方法中所有问题的根本原因。
        //如果我们使用栈并从左到右读取表达式的元素，则最终我们会从右到左计算表达式。
        // 就会出现 (A-B)-C(A−B)−C 等于 (C-B)-A(C−B)−A 的情况，这是不正确的。减法即不遵循结合律也不遵循交换律。
        //这个问题很容易解决，我们通过反转字符串，然后再按需添加到栈中，我们将字符串从右到左放入栈中，并从左到右正确的计算表达式。
        //
        // TODO 思路：
        //按逆序迭代字符串。
        //操作数可以由多个字符组成，字符串 "123" 表示数字 123，它可以被构造为：123 >> 120 + 3 >> 100 + 20 + 3。
        // 如果我们读取的字符是一个数字，则我们要将读取的数字乘以 10 的幂并将当前数字相加，形成操作数。因为我们是按逆序处理字符串。
        //操作数由多个字符组成，一旦我们遇到的字符不是数字，则我们将操作数添加到栈上。
        //当我们遇到最括号 (，这意味这遇到了一个子表达式结束。由于我们是逆序，所以开括号成了表达式的结尾。
        // 则需要从栈中弹出操作数和运算发来计算表达式，直到弹出相应的右括号。子表达式的最终结果最终添加到栈上。
        //将非数字字符添加到栈上。
        //这个做直到我们得到最终的结果。可能我们没有更多的字符要处理，但是栈仍然是非空的。当主表达式没有用括号括起来时，就会发生这种情况。
        // 因此，在完成对整个表达式求值之后，我们将检查栈是否非空。如果是的话，我们将栈中的元素作为最终表达式处理，
        // 并像遇到左括号时那样对其求值。我们还可以用一组括号覆盖原表达式，以此避免额外调用。
        //

        return 0;
    }












    public static void main(String[] args) {


        // boolean bool = isValid(")(){}");
        // int[][] pos = {{1,3},{-2,-2}};

        int[] ans = {2,1,5,6,2,3};
        largestRectangleArea2(ans);
        System.out.println("============================");
    }

}
